#ifndef LINKEDLIST_HPP
#define LINKEDLIST_HPP
/* ------------------------------------------------------------------
代码作者：MikeYang99
内容描述：cpp实现链表的增、删、改、查
文件描述：为解决​​模板类分离编译问题，使用.hpp文件，​​减少.cpp文件数量​​，避免多文件编译的复杂性
--------------------------------------------------------------------*/
#include <iostream>

template<typename T>                // 模板替换固定类型
struct Node
{
    T data;                         // 写法更简洁，Node在cpp可以直接用了
    Node<T>* next;                  // 使用模板参数T
};

template<typename T>
using pNode = Node<T>*;             // c++风格别名

template<typename T>
class LinkedList{
private:
    pNode<T> head = nullptr;        // 显式初始化头指针
public:
    // 头插法创建节点
    pNode<T> insertHead(T value){
        try {
            pNode<T> new_node = new Node<T>{value, nullptr};  // 可能抛出std::bad_alloc等异常
            new_node->next = head;
            head = new_node;
            return head;
        }
        catch (const std::bad_alloc& e) {  // 优先捕获特定异常
            std::cerr << "insertHead: Memory allocation failed," << e.what() << std::endl;
            return nullptr;
        }
        catch (...) {  // 捕获其他所有异常
            std::cerr << "insertHead: Unknown exception occurred" << std::endl;
            return nullptr;
        }
    }
    // 尾插法创建节点
    pNode<T> insertTail(T value){
        try {
            pNode<T> new_node = new Node<T>{value, nullptr};  // 可能抛出std::bad_alloc等异常
            if(!head){
                head = new_node;
            }else {
                pNode<T> cur_node = head;
                while (cur_node->next != nullptr) {
                    cur_node = cur_node->next;
                }
                cur_node->next = new_node;
            }
            return head;
        }
        catch (const std::bad_alloc& e) {  // 优先捕获特定异常
            std::cerr << "insertHead: Memory allocation failed," << e.what() << std::endl;
            return nullptr;
        }
        catch (...) {  // 捕获其他所有异常
            std::cerr << "insertHead: Unknown exception occurred" << std::endl;
            return nullptr;
        }
    }
    // 按值删除单个节点
    void popByVal(T value){
        if(!head){
            std::cout << "popByVal: The list is empty." << std::endl;
            return;
        }
        pNode<T> tmp_node = nullptr;
        // 值在头节点
        if(head->data == value){
            tmp_node = head;
            head = head->next;
            delete tmp_node;
            return;
        }
        // 值在尾部或中间
        pNode<T> cur_node = head,pre_node = nullptr;
        while ( (cur_node != nullptr) && (cur_node->data != value) ) {  // 找到值且当前节点不为空
            pre_node = cur_node;
            cur_node = cur_node->next;
        }
        // 如果没有匹配到值
        if(!cur_node){
            std::cout << "popByVal: No matching value was found." << std::endl;
        }else {
            tmp_node = cur_node;
            pre_node->next = cur_node->next;
            delete tmp_node;
        }
    }
    // 按索引删除节点
    void popByIdx(int index){
        if(!head){
            std::cout << "popByIdx: The list is empty." << std::endl;
            return;
        }
        if(index < 0){
            std::cout << "popByIdx: Invalid index." << std::endl;
            return;
        }
        int idx = 0;
        pNode<T> tmp_node = nullptr;
        if(idx == index){
            tmp_node = head;
            head = head->next;
            delete tmp_node;
            return;
        }
        pNode<T> pre_node = nullptr,cur_node = head;
        while ( (cur_node != nullptr)&&(idx != index) ) {       // 当前节点不为空且没有匹配到索引
            pre_node = cur_node;
            cur_node = cur_node->next;
            idx++;
        }
        // 没有找到索引
        if(!cur_node){
            std::cout << "popByIdx: Index out of range." << std::endl;
        }else {
            pre_node->next = cur_node->next;
            tmp_node = cur_node;
            delete tmp_node;
        }
    }
    // 显示所有数据
    void show(){
        if(!head){
            std::cout << "show: The list is empty." << std::endl;
            return;
        }
        std::cout << "The list data:  ";
        pNode<T> cur_node = head;
        while (cur_node != nullptr) {
            std::cout << cur_node->data << "  ";
            cur_node = cur_node->next;
        }
        std::cout << "\n";
    }
    // 释放堆内存
    void release(){
        if(!head){
            std::cout << "release: The list is empty." << std::endl;
            return;
        }
        int count;
        pNode<T> tmp_node = nullptr;
        pNode<T> cur_node = head;
        while (cur_node != nullptr) {
            tmp_node = cur_node;
            cur_node = cur_node->next;
            delete tmp_node;
            count++;
        }
        head = nullptr;             // 防止悬挂指针
        std::cout << "The list released " << count << " nodes." << std::endl;
    }
    // 防止没有显式调用release造成问题
    ~LinkedList<T>(){
        std::cout << "Destruction function called" << std::endl;
        release();
    }
};

#endif
